/*
 * @lc app=leetcode.cn id=46 lang=typescript
 *
 * [46] 全排列
 */

// @lc code=start

//  思路；回溯法
//  有约束的选择元素，已经被选择过的不能再选择，利用对象存储
//  被选择过的进行剪枝

//  复杂度：O(n×n!)，其中 n 为序列的长度。  O(n)
function permute(nums: number[]): number[][] {
    const res: number[][] = []
    const used = new Map()

    const dfs = (curr: number[]) => {
        if (curr.length === nums.length) {
            res.push(curr.slice())
            return
        }
        for (const num of nums) {
            if (used.get(num) === true) continue
            curr.push(num)
            used.set(num, true)
            dfs(curr)
            curr.pop()
            used.set(num, false)
        }
    }

    dfs([])
    return res
};
// @lc code=end


console.log(permute([1, 2, 3]))

export { }